package com.回溯法机器人运动范围;

public class Solution {
	public int movingCount(int threshold, int rows, int cols) {
		int[] canget = new int[rows * cols];
		findmovingarea(threshold, rows, cols, 0, 0, canget);
		return sum(canget);
	}

	public void findmovingarea(int k, int rows, int cols, int r, int c, int[] canget) {
		if (r < 0 || r >= rows || c < 0 || c >= cols || canget[r * cols + c] == 1 || count(r) + count(c) > k)
			return;
		canget[r * cols + c] = 1;
		findmovingarea(k, rows, cols, r + 1, c, canget);
		findmovingarea(k, rows, cols, r - 1, c, canget);
		findmovingarea(k, rows, cols, r, c + 1, canget);
		findmovingarea(k, rows, cols, r, c - 1, canget);
	}

	public int sum(int[] canget) {
		int sum = 0;
		for (int i = 0; i < canget.length; i++) {
			sum = sum + canget[i];
		}
		return sum;
	}

	public int count(int i) {
		int sum = 0;
		while(i>0) {
			sum = sum + i % 10;
			i = i / 10;
		}
		
		return sum;
	}
}
